import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution102 {

    class Pair<T1, T2>{
        T1 first;
        T2 second;

        public Pair(T1 first, T2 second) {
            this.first = first;
            this.second = second;
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){ return res; }
        Queue<Pair<TreeNode, Integer>> q = new LinkedList<>();
        q.add(new Pair<>(root, 0));
        for(int i = 0; !q.isEmpty(); i++){
            List<Integer> tmpList = new ArrayList<>();
            while(!q.isEmpty() && q.peek().second == i) {
                Pair<TreeNode, Integer> tmpInfo = q.poll();
                TreeNode tmpNode = tmpInfo.first;
                tmpList.add(tmpNode.val);
                if(tmpNode.left != null){
                    q.add(new Pair<>(tmpNode.left, i + 1));
                }
                if(tmpNode.right != null){
                    q.add(new Pair<>(tmpNode.right, i + 1));
                }
            }
            res.add(tmpList);
        }
        return res;
    }
}
